package datastructure;

import java.util.ArrayList;

public class MergeIntervals {
	static class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}
	}

	boolean[] seg, boarder;

	void init(int n) {
		seg = new boolean[n << 2];
		boarder = new boolean[n << 2];
	}

	void cover(int root, int l, int r, int i, int j) {
		if (seg[root] || l == i && r == j) {
			seg[root] = true;
			return;
		}
		int m = l + r >> 1;
		if (i > m)
			cover((root << 1) + 1, m + 1, r, i, j);
		else if (j <= m)
			cover(root << 1, l, m, i, j);
		else {
			boarder[root] = true;
			cover(root << 1, l, m, i, m);
			cover((root << 1) + 1, m + 1, r, m + 1, j);
		}
		if (boarder[root] && seg[root << 1] && seg[(root << 1) + 1])
			seg[root] = true;
	}

	void display(int root, int l, int r, boolean b) {
		if (seg[root]) {
			if (res.isEmpty()) {
				res.add(new Interval(l - 1, r - 1));
			} else {
				Interval prev = res.get(res.size() - 1);
				if (prev.end == l - 2 && b) {
					prev.end = r - 1;
				} else {
					res.add(new Interval(l - 1, r - 1));
				}
			}
			// System.out.println(l - 1 + " " + r);
			return;
		}
		if (l == r)
			return;
		int m = l + r >> 1;
		display(root << 1, l, m, b);
		display((root << 1) + 1, m + 1, r, boarder[root]);
	}

	ArrayList<Interval> res;

	public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
		int n = 10000;
		res = new ArrayList<Interval>();
		init(n);
		for (Interval i : intervals) {
			cover(1, 1, n, i.start + 1, i.end + 1);
		}
		display(1, 1, n, false);
		return res;
	}

	public static void main(String[] args) {
		MergeIntervals a = new MergeIntervals();
		ArrayList<Interval> intervals = new ArrayList<Interval>();
		Interval i = new Interval(1, 3);
		intervals.add(i);
		i = new Interval(2, 6);
		intervals.add(i);
		i = new Interval(8, 10);
		intervals.add(i);
		i = new Interval(15, 18);
		intervals.add(i);
		ArrayList<Interval> res = a.merge(intervals);
		for (Interval ii : res) {
			System.out.println(ii.start + " " + ii.end);
		}
	}
}
